package com.caochenlei.linkedList;

/**
 * 单向循环链表实现代码
 */
public class DoublyCircularLinkedList<E> {
    //定义结点类
    public class Node {
        Node prev;  //指向上个结点
        E data;     //代表结点数据
        Node next;  //指向下个结点

        public Node(E data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return "Node{data=" + data + "}";
        }
    }

    private Node head;  //代表链表头部
    private Node last;  //代表链表尾部
    private int size;   //代表链表长度

    public DoublyCircularLinkedList() {
        //头结点应该指向第一个结点，现在没有，所以为null
        this.head = null;
        //尾结点应该指向最后的结点，现在没有，所以为null
        this.last = null;
        this.size = 0;
    }

    //获取链表当前大小
    public int size() {
        return size;
    }

    //判断链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    //检查下标是否合法
    public void checkIndex(int index) {
        if (index < 0 || (size - 1) < index) {
            throw new IndexOutOfBoundsException("链表下标越界异常，请检查链表的下标！");
        }
    }

    //连接链表两个结点
    public void connectNode(Node prevNode, Node nextNode) {
        if (prevNode != null) {
            prevNode.next = nextNode;
        }
        if (nextNode != null) {
            nextNode.prev = prevNode;
        }
    }

    //释放链表指定结点
    public void releaseNode(Node node) {
        if (node != null) {
            node.prev = null;
            node.data = null;
            node.next = null;
        }
    }

    //返回链表最后结点
    public Node getLast() {
        //判断链表是否为空
        if (isEmpty()) {
            return null;
        }
        //返回链表最后结点
        return last;
    }

    //返回链表首个结点
    public Node getFirst() {
        //判断链表是否为空
        if (isEmpty()) {
            return null;
        }
        //返回链表首个结点
        return head;
    }

    //获取指定位置结点
    public Node getIndex(int index) {
        //检查下标是否合法
        checkIndex(index);
        //获取指定位置结点
        Node curNode = head;
        for (int i = 0; i < index; i++) {
            curNode = curNode.next;
        }
        //返回指定位置结点
        return curNode;
    }

    //获取位置之前结点
    private Node getIndexPre(int index) {
        return getIndex(index).prev;
    }

    //链表尾后添加数据
    public void addLast(E e) {
        //判断链表是否为空
        if (isEmpty()) {
            //创建新的结点
            Node newNode = new Node(e);
            //修改头尾指向
            head = newNode;
            last = newNode;
            //自己连接自己
            connectNode(newNode, newNode);
        } else {
            //获取last结点
            Node oldLast = last;
            //创建新的结点
            Node newLast = new Node(e);
            //修改last指向
            last = newLast;
            //头尾连接成环
            connectNode(oldLast, newLast);
            connectNode(newLast, head);
        }
        //链表链表长度加一
        size++;
    }

    //链表头后添加数据
    public void addFirst(E e) {
        //判断链表是否为空
        if (isEmpty()) {
            addLast(e);
            return;
        } else {
            //获取head结点
            Node oldHead = head;
            //创建新的结点
            Node newHead = new Node(e);
            //修改head指向
            head = newHead;
            //头尾连接成环
            connectNode(last, newHead);
            connectNode(newHead, oldHead);
        }
        //链表链表长度加一
        size++;
    }

    //指定位置添加数据
    public void addIndex(int index, E e) {
        //获取位置之前结点
        Node preNode = getIndexPre(index);
        //获取指定位置结点
        Node curNode = preNode.next;
        //创建一个新的结点
        Node newNode = new Node(e);
        //开始三个结点连接
        connectNode(preNode, newNode);
        connectNode(newNode, curNode);
        //修改head的指向
        if (curNode == head) {
            head = newNode;
        }
        //当前链表长度加一
        size++;
    }

    //删除指定位置结点
    public void removeIndex(int index) {
        //获取位置之前结点
        Node preNode = getIndexPre(index);
        //获取指定位置结点
        Node curNode = preNode.next;
        //获取位置之后结点
        Node nexNode = curNode.next;
        //如果只有一个结点
        if (size == 1) {
            //修改head的指向
            head = null;
            //修改last的指向
            last = null;
            //释放链表指定结点
            releaseNode(preNode);
            releaseNode(curNode);
            releaseNode(nexNode);
            //当前链表长度减一
            size--;
        } else {
            //修改head的指向
            if (curNode == head) {
                head = nexNode;
            }
            //修改last的指向
            if (curNode == last) {
                last = preNode;
            }
            //删除指定位置结点
            connectNode(preNode, nexNode);
            //释放链表指定结点
            releaseNode(curNode);
            //当前链表长度减一
            size--;
        }
    }

    //删除链表首个结点
    public void removeFirst() {
        //判断链表是否为空
        if (isEmpty()) {
            return;
        }
        //删除链表首个结点
        removeIndex(0);
    }

    //删除链表最后结点
    public void removeLast() {
        //判断链表是否为空
        if (isEmpty()) {
            return;
        }
        //获取位置之前结点
        Node preNode = last.prev;
        //获取指定位置结点
        Node curNode = last;
        //获取位置之后结点
        Node nexNode = last.next;
        //如果只有一个结点
        if (size == 1) {
            //修改head的指向
            head = null;
            //修改last的指向
            last = null;
            //释放链表指定结点
            releaseNode(preNode);
            releaseNode(curNode);
            releaseNode(nexNode);
            //当前链表长度减一
            size--;
        } else {
            //修改head的指向
            if (curNode == head) {
                head = nexNode;
            }
            //修改last的指向
            if (curNode == last) {
                last = preNode;
            }
            //删除指定位置结点
            connectNode(preNode, nexNode);
            //释放链表指定结点
            releaseNode(curNode);
            //当前链表长度减一
            size--;
        }
    }

    //输出链表所有结点
    public void show() {
        //判断链表是否为空
        if (isEmpty()) {
            return;
        }
        //遍历链表所有结点
        Node curNode = head;
        do {
            System.out.println(curNode);
            curNode = curNode.next;
        } while (curNode != head);
    }

    //反转链表所有结点
    public void reverse() {
        //判断链表是否为空
        if (isEmpty()) {
            return;
        }
        //创建一个临时节点
        Node newHead = new Node(null);
        //循环遍历圆环结点
        Node newFirst;
        Node tmpNode;
        Node curNode = head;
        do {
            //缓存当前结点下个结点
            tmpNode = curNode.next;
            //获取临时结点首结点
            newFirst = newHead.next;
            //开始三个结点进行关联
            connectNode(newHead, curNode);
            connectNode(curNode, newFirst);
            //让当前的结点往后移动
            curNode = tmpNode;
        } while (curNode != head);
        //交换旧头尾指向
        tmpNode = head;
        head = last;
        last = tmpNode;
        //首尾相连成圆环
        connectNode(last, newHead.next);
        //释放新建临时节点
        releaseNode(newHead);
    }

    //清空链表所有结点
    public void clear() {
        //判断链表是否为空
        if (isEmpty()) {
            return;
        }
        //遍历链表所有结点
        Node tmpNode;
        Node curNode = head;
        do {
            //缓存下个结点
            tmpNode = curNode.next;
            //释放当前结点
            releaseNode(curNode);
            //移动下个结点
            curNode = tmpNode;
        } while (curNode != head);
        //重置链表基本信息
        head = null;
        last = null;
        size = 0;
    }

    //顺序查找数据首次出现位置
    public int indexOf(E e) {
        //判断链表是否为空
        if (isEmpty()) {
            return -1;
        }
        //判断对象是否为空
        if (e == null) {
            return -1;
        }
        //获取指定位置结点
        Node curNode = head;
        for (int i = 0; i < size; i++) {
            if (e.equals(curNode.data)) {
                return i;
            }
            curNode = curNode.next;
        }
        //没有找到返回负一
        return -1;
    }

    //逆序查找数据首次出现位置
    public int lastIndexOf(E e) {
        //判断链表是否为空
        if (isEmpty()) {
            return -1;
        }
        //判断对象是否为空
        if (e == null) {
            return -1;
        }
        //获取指定位置结点
        Node curNode = last;
        for (int i = 0; i < size; i++) {
            if (e.equals(curNode.data)) {
                return i;
            }
            curNode = curNode.prev;
        }
        //没有找到返回负一
        return -1;
    }
}
